#include "Sort.h"

#include "Timer.h"

#include <algorithm>
#include <iostream>
#include <limits>
#include <vector>

int* g_attributeOrder;
int* g_bestAttributeOrder;
unsigned int g_lowestIntersectionCount;
const unsigned int* g_intersections;
unsigned int g_attributeCount;
unsigned int g_attributeSize;

#define SHOWRESULTS 0

void RecursiveSort(int p_level)
{
	if (p_level > 1)
	{
		for (int i = 0; i < p_level; ++i)
		{
			std::swap(g_attributeOrder[i], g_attributeOrder[p_level-1]);
			RecursiveSort(p_level - 1);
			std::swap(g_attributeOrder[i], g_attributeOrder[p_level-1]);
		}
	}
	else
	{
		// Check if number intersections is lower than the lowest found so far.
		unsigned int intersectionCount = 0;
		for (unsigned int i = 0; i < g_attributeCount-1; ++i)
		{
			intersectionCount += g_intersections[g_attributeOrder[i] * g_attributeCount + g_attributeOrder[i + 1]];
		}
		if (intersectionCount < g_lowestIntersectionCount)
		{
			g_lowestIntersectionCount = intersectionCount;
			memcpy(g_bestAttributeOrder, g_attributeOrder, g_attributeSize);
		}
	}
}

void Sort::bruteForceSort(const unsigned int* p_intersections, unsigned int p_attributeCount, 
						  unsigned int& p_intersectionCount, int*& p_attributeOrder, float& p_time)
{
	Timer timer;	

	// set it to a very high number
	g_lowestIntersectionCount = std::numeric_limits<unsigned int>::max();
	g_attributeOrder = new int[p_attributeCount];
	for (unsigned int i = 0; i < p_attributeCount; ++i)
	{
		g_attributeOrder[i] = i;
	}
	g_bestAttributeOrder = new int[p_attributeCount];
	p_attributeOrder = g_bestAttributeOrder;

	g_intersections = p_intersections;
	g_attributeCount = p_attributeCount;
	g_attributeSize = g_attributeCount * sizeof(unsigned int);

	timer.update();
	RecursiveSort(static_cast<int>(p_attributeCount));
	timer.update();
	p_time = timer.getSeconds();

	p_intersectionCount = g_lowestIntersectionCount;

	delete[] g_attributeOrder;

#if SHOWRESULTS
	std::cout << "Brute force results\nIntersections: " << p_intersectionCount << std::endl;

	for (unsigned int i = 0; i < p_attributeCount; ++i)
	{
		std::cout << p_attributeOrder[i] << " ";
	}
	std::cout << std::endl;

	std::cout << "Calculation time: " << timer.getSeconds() << " seconds." << std::endl << std::endl;	
#endif
}

//int* g_attributeOrder;
//int* g_bestAttributeOrder;
//unsigned int g_lowestIntersectionCount;
//const unsigned int* g_intersections;
//unsigned int g_attributeCount;
//unsigned int g_attributeSize;
unsigned int g_startIndex;
unsigned int g_countStartIndex;
unsigned int g_countSize;

// Recursive sort for part of the attributes
void partialRecursiveSort(unsigned int p_level)
{
	if (p_level > 1)
	{
		for (unsigned int i = g_startIndex; i < p_level + g_startIndex; ++i)
		{
			std::swap(g_attributeOrder[i], g_attributeOrder[g_startIndex + p_level-1]);
			partialRecursiveSort(p_level - 1);
			std::swap(g_attributeOrder[i], g_attributeOrder[g_startIndex + p_level-1]);
		}
	}
	else
	{
		// Check if number intersections is lower than the lowest found so far.
		unsigned int intersectionCount = 0;
		for (unsigned int i = g_countStartIndex; i < g_countStartIndex + g_countSize-1; ++i)
		{
			intersectionCount += g_intersections[g_attributeOrder[i] * g_attributeCount + g_attributeOrder[i + 1]];
		}
		if (intersectionCount < g_lowestIntersectionCount)
		{
			g_lowestIntersectionCount = intersectionCount;
			memcpy(&g_bestAttributeOrder[g_startIndex], &g_attributeOrder[g_startIndex], g_attributeSize);
		}
	}
}

unsigned int getBinaryNumberWithNOnes(unsigned int n)
{
	unsigned int binaryNumber = 0;
	for (unsigned int i = 0; i < n; ++i)
	{
		binaryNumber += 1 << i;
	}
	return binaryNumber;
}

void Sort::bruteForceSortDynamic(const unsigned int* p_intersections, unsigned int p_attributeCount, 
								 unsigned int& p_intersectionCount, int*& p_attributeOrder, float& p_time)
{
	unsigned int bitsInUnsignedInt = sizeof(unsigned int) * 8;
	if (p_attributeCount > bitsInUnsignedInt)
	{
		std::cout << "Warning, attribute count can't be higher than " << bitsInUnsignedInt << "." << std::endl;
		return;
	}

	g_attributeOrder = new int[p_attributeCount];
	g_bestAttributeOrder = new int[p_attributeCount];
	int* bestAttributeOrder = new int[p_attributeCount];
	p_intersectionCount = std::numeric_limits<unsigned int>::max();

	p_attributeOrder = bestAttributeOrder;

	g_intersections = p_intersections;
	g_attributeCount = p_attributeCount;

	Timer timer;
	timer.update();
	
	// Determine the index of the middle element. For an even number of attributes 
	// there are two elements in the middle, we take the one on the right.
	const unsigned int attributesOnLeft = p_attributeCount / 2;
	const unsigned int attributesOnRight = p_attributeCount / 2 - ((p_attributeCount + 1) % 2);
	const unsigned int middleIndex = p_attributeCount / 2;

	// Max value is a binary number with n ones in a row.
	const unsigned int maxValueForDistribution = getBinaryNumberWithNOnes(p_attributeCount);	

	// Try all attributes as the middle node
	for (unsigned int i = 0; i < p_attributeCount; ++i)
	{
		g_attributeOrder[middleIndex] = i;
		g_bestAttributeOrder[middleIndex] = i;

		// The bits that determine which elements will be on the left and right part of the middle element.
		unsigned int elementDistributionBits = 0;

		while (elementDistributionBits <= maxValueForDistribution)
		{
			unsigned int numberOfOnes = 0;
			unsigned int distributionCopy = elementDistributionBits;
			// Count the number of ones in the distribution
			for (unsigned int j = 0; j < p_attributeCount; ++j)
			{
				if (distributionCopy % 2 == 1)
				{
					if (j != i) // j != i so we don't count the element in the middle
					{
						++numberOfOnes;
					}
					else
					{
						// Skip this one so we don't do every distribution twice.
						numberOfOnes = 0;
						break;
					}
				}
				distributionCopy = distributionCopy >> 1;
			}
			
			distributionCopy = elementDistributionBits;
			if (numberOfOnes == attributesOnLeft)
			{
				unsigned int leftIndex = 0;
				unsigned int rightIndex = middleIndex + 1;
				// Create the attribute order
				for (unsigned int j = 0; j < p_attributeCount; ++j)
				{
					// Skip middle element
					if (j != i)
					{
						// Uneven number
						if (distributionCopy & 1)
						{
							// left element
							g_attributeOrder[leftIndex] = j;
							++leftIndex;
						}
						else
						{
							// right element
							g_attributeOrder[rightIndex] = j;
							++rightIndex;
						}
					}
					distributionCopy = distributionCopy >> 1;
				}

				// Find the best order for the left and right distribution.
				// Left.
				g_startIndex = 0;
				g_countStartIndex = 0;
				g_countSize = attributesOnLeft + 1;
				g_lowestIntersectionCount = std::numeric_limits<unsigned int>::max();
				g_attributeSize = attributesOnLeft * sizeof(unsigned int);
				partialRecursiveSort(attributesOnLeft);

				unsigned int intersectionCount = g_lowestIntersectionCount;

				// Right.
				g_startIndex = middleIndex + 1;
				g_countStartIndex = middleIndex;
				g_countSize = attributesOnRight + 1;
				g_lowestIntersectionCount = std::numeric_limits<unsigned int>::max();
				g_attributeSize = attributesOnRight * sizeof(unsigned int);
				partialRecursiveSort(attributesOnRight);

				intersectionCount += g_lowestIntersectionCount;

				if (intersectionCount < p_intersectionCount)
				{
					memcpy(bestAttributeOrder, g_bestAttributeOrder, p_attributeCount * sizeof(int));
					p_intersectionCount = intersectionCount;
				}
			}

			++elementDistributionBits;
		}
	}

	timer.update();
	p_time = timer.getSeconds();

	delete[] g_attributeOrder;
	delete[] g_bestAttributeOrder;

#if SHOWRESULTS
	std::cout << "Brute force results\nIntersections: " << p_intersectionCount << std::endl;

	for (unsigned int i = 0; i < p_attributeCount; ++i)
	{
		std::cout << p_attributeOrder[i] << " ";
	}
	std::cout << std::endl;

	std::cout << "Calculation time: " << timer.getSeconds() << " seconds." << std::endl << std::endl;	
#endif
}

void Sort::heuristicSort(const unsigned int* p_intersections, unsigned int p_attributeCount, 
						 unsigned int& p_intersectionCount, int*& p_attributeOrder, float& p_time)
{
	// set it to a very high number
	p_intersectionCount = std::numeric_limits<unsigned int>::max();
	p_attributeOrder = 0;

	Timer timer;

	timer.update();

	// Find the best starting axis
	for (unsigned int i = 0; i < p_attributeCount; ++i)
	{
		unsigned int intersectionCount = 0;
		int* attributeOrder = new int[p_attributeCount];
		// set i as first attribute
		attributeOrder[0] = i;

		// remaining attributes
		std::vector<int> remainingAttributes;
		for (unsigned int j = 0; j < p_attributeCount; ++j)
		{
			if (j != i)
				remainingAttributes.push_back(j);
		}

		for (unsigned int j = 1; j < p_attributeCount; ++j)
		{
			// Find the best next axis.
			unsigned int lowestFound = std::numeric_limits<int>::max();
			unsigned int nextAttributeIndex = 0;
			int nextAttribute = remainingAttributes[0];
			for (unsigned int k = 0; k < remainingAttributes.size(); ++k)
			{
				const unsigned int intersections = p_intersections[attributeOrder[j-1] * p_attributeCount + remainingAttributes[k]];
				
				if (intersections < lowestFound)
				{
					nextAttributeIndex = k;
					nextAttribute = remainingAttributes[k];
					lowestFound = intersections;
				}
			}

			remainingAttributes.erase(remainingAttributes.begin() + nextAttributeIndex);
			attributeOrder[j] = nextAttribute;
			intersectionCount += lowestFound;
		}

		// is this starting attribute better?
		if (intersectionCount < p_intersectionCount)
		{
			p_intersectionCount = intersectionCount;
			delete[] p_attributeOrder;
			p_attributeOrder = attributeOrder;
		}
		else
		{
			delete[] attributeOrder;
		}
	}

	timer.update();
	p_time = timer.getSeconds();

#if SHOWRESULTS
	std::cout << "Heuristic results\nIntersections: " << p_intersectionCount << std::endl;
	for (unsigned int i = 0; i < p_attributeCount; ++i)
	{
		std::cout << p_attributeOrder[i] << " ";
	}
	std::cout << std::endl;

	std::cout << "Calculation time: " << timer.getSeconds() << " seconds." << std::endl << std::endl;
#endif
}

Sort::Sort()
{
}

Sort::~Sort()
{
}
